package com.zjsru.plan2024.week;

import java.util.Arrays;

/**
 * 3085. 成为 K 特殊字符串需要删除的最少字符数
 * 如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立，则认为 word 是 k 特殊字符串。
 * @Author: cookLee
 * @Date: 2024-03-20
 */
public class MinimumDeletions {

    /**
     * 主
     * \
     * 输入：word = "aabcaba", k = 0
     * 输出：3
     * 解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。
     * \
     * 输入：word = "dabdcbdcdcd", k = 2
     * 输出：2
     * 解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinimumDeletions minimumDeletions = new MinimumDeletions();
        String word = "aabcaba";
        int k = 0;
        System.out.println(minimumDeletions.minimumDeletions(word, k));
    }

    /**
     * 最小删除
     *
     * @param word 字
     * @param k    k
     * @return int
     */
    public int minimumDeletions(String word, int k) {
        //定义一个数组来存储各个字母出现的次数
        int[] nums = new int[26];
        for (char c : word.toCharArray()) {
            nums[c - 'a']++;
        }
        Arrays.sort(nums);
        //定义一个对象来记录最多保留的字母数
        int maxSave = 0;
        //26个字母内循环，定义nums[i]用来作为比较的基础
        for (int i = 0; i < 26; i++) {
            int sum = 0;
            for (int j = i; j < 26; j++) {
                // 字母至多保留 cnt[i]+k 个
                sum += Math.min(nums[j], nums[i] + k);
            }
            maxSave = Math.max(maxSave, sum);
        }
        //相减即是最小可删除的字母数
        return word.length() - maxSave;
    }

}
